package kyssion.leetcode.num1_50;

public class code45_跳跃游戏 {
    public static void main(String[] args) {
        System.out.println(new code45_跳跃游戏().jump(
                new int[]{
                       2,3,1,1,4
                }
        ));
    }

    /**
     * 这个是从跳数的维度来思考问题的
     * @param nums
     * @return
     */
    public int jump(int[] nums) {
        if (nums.length <= 1) {
            return 0;
        }
        int left = 0, right = 1;
        int speed = 0;
        while (left < right) {
            int maxRight = 0;
            while (left < right) {
                maxRight = Math.max(maxRight, nums[left] + left);
                left++;
            }
            speed++;
            if (maxRight >= nums.length - 1) {
                break;
            }
            left = right;
            right = maxRight + 1;
        }
        return speed;
    }

    /**
     * 第二种方法,其实是一种思想上的优化,找到通用的点
     * 思维很怪,,,开始的时候我计算了第x跳能到达的位置,接下来的遍历都是在计算吓一跳的位置
     * 当我遍历到第一跳的时候结尾的时候,表示第一跳能得到的所有第二跳的位置已经遍历清除了,开始执行第一步
     * @param nums
     * @return
     */
    public int jump2(int[] nums) {
        if(nums.length == 1) return 0;
        int reach = 0;
        int nextreach = nums[0];
        int step = 0;
        for(int i = 0;i<nums.length;i++){
            nextreach = Math.max(i+nums[i],nextreach);
            if(nextreach >= nums.length-1) return (step+1);
            if(i == reach){
                step++;
                reach = nextreach;
            }
        }
        return step;
    }

}
